package com.xiaoyu.arrays;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: DS_and_A
 * @description: 杨辉三角!
 *
 * 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
 * 在杨辉三角中，每个数是它左上方和右上方的数的和。
 * 输入: 5
 * 输出:
 * [
 *      [1],
 *     [1,1],
 *    [1,2,1],
 *   [1,3,3,1],
 *  [1,4,6,4,1]
 * ]
 *
 * @author: YuWenYi
 * @create: 2021-05-27 15:53
 **/
public class YangHuiTriangle_118{

    //方法一:双重for循环!
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows == 0) return res;  //特判
        for (int i = 0; i < numRows; i++) {   //第几行!
            ArrayList<Integer> list = new ArrayList<>();
            for (int j = i ; j >= 0; j--) {   //每行的元素个数以及它们的索引
                if (i != 0){
                    List<Integer> preList = res.get(i - 1); //获取上一行的元素
                    Integer num1 = j > preList.size()-1 ? 0 : preList.get(j); //获取上一行当前索引的值
                    Integer num2 = j - 1 < 0 ? 0 : preList.get(j-1);  //获取上一行当前索引-1的值
                    list.add(num1+num2); //让他们相加
                }else {
                    list.add(1);
                }
            }
            res.add(list);
        }
        return res;
    }

    //方法二:较为优化的写法
    public static List<List<Integer>> generate1(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows == 0) return res;
        res.add(new ArrayList<Integer>(){{add(1);}});
        if (numRows == 1) return res;
        res.add(new ArrayList<Integer>(){{add(1); add(1);}});
        if (numRows == 2) return res;
        List<Integer> preRow = res.get(1);
        for (int i = 3; i <= numRows; i++) {
            List<Integer> list = new ArrayList<Integer>(){{add(1);}};
            for (int j = 1; j < i - 1; j++) {
                list.add(preRow.get(j) + preRow.get(j - 1));
            }
            list.add(1);
            preRow = list;
            res.add(list);
        }
        return res;
    }

    public static void main(String[] args) {
        generate1(8).forEach(System.out::println);
    }

}
